/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/graph-valid-tree
   @Language: C++
   @Datetime: 17-03-30 14:27
   */

class Solution {
public:
	/**
	 * @param n an integer
	 * @param edges a list of undirected edges
	 * @return true if it's a valid tree, or false
	 * Tip: No circle and connected graph, is a tree
	 *      Using BFS traversal, record each node's father
	 *    1)if g equal to q's father, treat edge <g,q>, <q,g>
	 *      as the same edge (undirected graph).
	 *    2)if visit a node more than once, the graph has circle
	 *    3)if the number of visited nodes not equal to n, not connected
	 */
	bool validTree(int n, vector<vector<int> > &edges) {
		// Write your code here
		if (n==1 && edges.size()==0) return true;
		unordered_map<int,unordered_set<int> > graph;
		for(const auto &e : edges){
			graph[e[0]].insert(e[1]);
			graph[e[1]].insert(e[0]);
		}
		if (graph.size()!=n) return false;	// has single node
		queue<int> que;
		que.push(graph.begin()->first);
		unordered_map<int,int> vist;		// <node,father>
		for(vist[que.front()]=-1; que.size(); que.pop()){
			int q = que.front();
			for(const auto &g : graph[q]){
				if (g==vist[q]) continue;	// undirected edge
				if (vist.find(g)!=vist.end()) return false;	// has circle
				que.push(g);
				vist[g]=q;					// record g's father
			}
		}
		return vist.size()==n;				// if not connected
	}
};
